package cxydmmszl.chapter05.t085.middle;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 完美洗牌问题
 * <li style="color: green;">Desc</li>
 * 给定一个长度为偶数的数组arr，长度记为 2*N。前 n 个为左部分，后 n 个为右部分。
 * arr可以表示为{L1,L2...L(n-1),Ln,R1,R2...R(n-1),Rn}，
 * 请将数组调整成{R1,L1,R2,L2,...R(n-1),L(n-1),Rn,Ln}。
 * <li style="color: green;">Input</li>
 * 输入有包含两行，第一行包含一个整数 n（1≤n≤10^5，保证 n 为偶数），代表 arr 长度。
 * 第二行包含 n 个整数，代表数组 arr（1≤arr[i]≤10^8）。
 * <li style="color: green;">Output</li>
 * 输出一行n个整数，代表调整后的数组arr。
 * <li style="color: blue;">Link</li> CD118
 *
 * @author habitplus
 * @since 2021-09-09 09:20
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return 0;
    }

    public static void main(String[] args) {
        int n = nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        absoluteExchange3(arr);

        StringBuilder sb = new StringBuilder();
        for (int e : arr) {
            sb.append(e).append(" ");
        }
        System.out.println(sb.toString());
    }

    /*
        洗牌算法：O(N) + O(1)
     */
    private static void absoluteExchange3(int[] arr) {
        if (arr != null && arr.length > 0 && (arr.length & 1) == 0) {
            shuffle(arr, 0, arr.length - 1);
        }
    }

    // 在 arr[l...r] 上做完美洗牌调整
    public static void shuffle(int[] arr, int l, int r) {

        // 切成一块一块的解决，每一块的长度满足 (3^k)-1
        while (r - l + 1 > 0) {
            int len = r - l + 1;


            // 计算 <=len 且距离 len 最近的，满足 (3^k)-1 的数
            // 也就是找到最大的 k，满足 3^k <= len + 1
            int base = 3, k = 1;
            while (base <= (len + 1) / 3) {
                base *= 3;
                k++;
            }

            // 当前要解决长度为 base - 1 的块，一半就是再除以 2
            int half = (base - 1) / 2;

            // [l...r] 的中点位置
            int mid = (l + r) / 2;

            // 要旋转的左部分为 arr[l+half, mid]，右部分为 arr[mid+1, mid+half]
            // 注意，这里 arr 下标是从 0 开始的
            rotate(arr, l + half, mid, mid + half);

            // 旋转完成后，从 l 开始算起，长度为 base-1 的部分进行下标连续推
            cycles(arr, l, base - 1, k);

            l = l + base - 1;
        }
    }

    // 从 start 位置开始，往右 len 的长度这一段做下标连续推
    // 出发位置依次为 1,3,9...
    private static void cycles(int[] arr, int start, int len, int k) {
        int preVal, cur, tmp;
        // 找到每一个出发位置 trigger，一共 k 个
        // 每一个 trigger 都进行下标连续推
        // 出发位置是从 1 开始算，而数组下标是从 0 开始
        for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
            preVal = arr[trigger + start - 1];
            cur = modifyIndex(trigger, len);
            while (cur != trigger) {
                tmp = arr[cur + start - 1];
                arr[cur + start - 1] = preVal;
                preVal = tmp;
                cur = modifyIndex(cur, len);
            }

            arr[cur + start - 1] = preVal;
        }
    }

    // [l,m] 为左部分，[m+1,r] 为右部分，左右两部分互换
    private static void rotate(int[] arr, int l, int m, int r) {
        reverse(arr, l, m);
        reverse(arr, m + 1, r);
        reverse(arr, l, r);
    }

    // 翻转 arr[l,r]
    private static void reverse(int[] arr, int l, int r) {
        int t;
        while (l < r) {
            t = arr[l];
            arr[l++] = arr[r];
            arr[r--] = t;
        }
    }

    // 数组的长度为 len，调整前的位置是 i，返回调整之后的位置
    // 下标得从 1 开始
    public static int modifyIndex(int i, int len) {
        return (2 * i) % (len + 1);
    }


    /*
        使用辅助空间：O(N)
     */
    private static void absoluteExchange2(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length % 2 != 0) {
            return;
        }

        int size = arr.length / 2;
        int[] aux = new int[size];

        for (int i = 0; i < size; i++) aux[i] = arr[i];

        for (int i = 0; i < size; i++) arr[2 * i] = arr[size + i];

        for (int i = 0; i < size; i++) arr[2 * i + 1] = aux[i];

    }

    /*
        时间复杂度 O(N^2)
     */
    private static void absoluteExchange1(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length % 2 != 0) {
            return;
        }

        int n = arr.length;

        for (int i = 0; i < n / 2; i++) {
            leftExchange(arr, i, n - 1 - i, n / 2 - i);
        }

    }

    private static void leftExchange(int[] arr, int l, int r, int size) {
        int j = r - size + 1;
        int t;
        while (j <= r) {
            t = arr[l];
            arr[l] = arr[j];
            arr[j] = t;
            l++;
            j++;
        }
    }
}
